//
// Created by francklinson on 2021/6/19.
//
//给定一个字符串数组 arr，字符串 s 是将 arr 某一子序列字符串连接所得的字符串，如果 s 中的每一个字符都只出现过一次，那么它就是一个可行解。
//
//请返回所有可行解 s 中最长长度。
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
#include <vector>
#include <string>
#include <iostream>

using namespace std;

class Solution {
private:
    int ans = 0;
public:
    int maxLength(vector<string> &arr) {
        /**
         * 用一个最多26位的数来代表字符串中出现了哪些字符
         */
        vector<int> masks;
        for (string &s : arr) {
            int mask = 0;
            for (char ch : s) {
                ch -= 'a';
                if ((mask >> ch) & 1) { // 若 mask 已有 ch，则说明 s 含有重复字母，无法构成可行解
                    mask = 0;
                    break;
                }
                mask |= 1 << ch; // 将 ch 加入 mask 中
            }
            if (mask > 0) {
                masks.push_back(mask); //masks中包含所有只含一个字母的字符串
            }
        }

        backtrack(0, 0, masks); // 调用递归函数
        return ans;
    }

    void backtrack(int pos, int mask, vector<int> &masks) {
        /**
         * 递归函数  pos表示进行到masks的第几个字符串，mask表示当前的结果
         */
        if (pos == masks.size()) {
            ans = max(ans, __builtin_popcount(mask)); //内置函数计算一个数字有多少位的1
            return;
        }
        if ((mask & masks[pos]) == 0) { // mask 和 masks[pos] 无公共元素
            backtrack(pos + 1, mask | masks[pos], masks);
        }
        backtrack(pos + 1, mask, masks);
    }
};

class Solution2 {
public:
    int maxLength(vector<string> &arr) {
        int ans = 0;
        vector<int> masks = {0}; // 解集合
        for (string &s : arr) {
            int mask = 0;
            for (char ch : s) {
                ch -= 'a';
                if ((mask >> ch) & 1) { // 若 mask 已有 ch，则说明 s 含有重复字母，无法构成可行解
                    mask = 0;
                    break;
                }
                mask |= 1 << ch; // 将 ch 加入 mask 中
            }
            if (mask == 0) {
                continue;
            }
            int n = masks.size();
            for (int i = 0; i < n; ++i) { // 遍历已有的解集
                int m = masks[i];
                if ((m & mask) == 0) { // m 和 mask 无公共元素
                    masks.push_back(m | mask);
                    ans = max(ans, __builtin_popcount(m | mask));
                }
            }
        }
        return ans;
    }
};

int main() {
    vector<string> arr{"un", "iq", "ue"};
    Solution sol;
    cout << sol.maxLength(arr) << endl;
    return 0;
}